#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) debug( __VA_ARGS__) 
#else
#define debug(...)
#endif

typedef struct node_t{
	int				data;
	struct node_t	*left;
	struct node_t	*right;
	struct node_t	*parent;
}node_t;

void create_tree(node_t **proot, node_t *parent)
{
	int		data;
	node_t	*node;

	while (scanf("%d", &data) != EOF) {
		debug("create node %d\n", data);
		node = (node_t *)malloc(sizeof(node_t));	
		node->data = data;
		node->parent = parent;
		create_tree(&node->left, node);
		create_tree(&node->right, node);
		*proot = node;
	}
}

void preorder_tree(node_t *root)
{
	if (root) {
		debug("%d\n", root->data);
		preorder_tree(root->left);
		preorder_tree(root->right);
	}
}

void inorder_tree(node_t *root)
{
	if (root) {
		inorder_tree(root->left);
		printf("%d\n", root->data);
		inorder_tree(root->right);
	}
}

void insert(node_t **p, int data)
{
	node_t	*q;

	q = NULL;
	while (*p) {
		if ((*p)->data == data)  return;
		if (data < (*p)->data) {
			q = *p;
			p = &(*p)->left;
			debug("%d insert into %d's left tree\n", data, q->data);
		}
		else {
			q = *p;
			p = &(*p)->right;
			debug("%d insert into %d's right tree\n", data, q->data);
		}
	}
	*p = malloc(sizeof(node_t));
	(*p)->data = data;
	(*p)->left = NULL;
	(*p)->right = NULL;
	(*p)->parent = q;
	debug("\n");
}

node_t *search(node_t *root, int key)
{
	while (root) {
		if (root->data == key) return root;
		if (key < root->data) {
			root = root->left;
		}
		else {
			root = root->right;
		}
	}

	return NULL;
}

node_t *successor(node_t *x)
{
	node_t 	*p, *q;

	for (p = x->right; p && p->left; p = p->left);
	if (p) return p;
	for (q = x, p = x->parent; p && p->left != q; q = p, p = p->parent);
	return p;
}

void delete(node_t **proot, node_t *z)
{
	node_t	*x, *y;

	if (z->left == NULL || z->right == NULL) {
		y = z;
	} else {	/* 有两个孩子，则删除其后继节点 */
		y = successor(z);
		z->data = y->data;
	}
	//此时y至多只有一个孩子, 接下来删除y
	x = y->left == NULL ? y->right : y->left;
	if (x) {
		x->parent = y->parent;
	}
	if (y->parent) {
		if (y == y->parent->left) {
			y->parent->left = x;
		} else {
			y->parent->right = x;
		}
	} else {	/* y是根节点 */
		*proot = x;
	}
	free(y);
}

int main()
{
	node_t		*root;

	root = NULL;

	insert(&root, 15);
	insert(&root, 5);
	insert(&root, 16);
	insert(&root, 3);
	insert(&root, 12);
	insert(&root, 20);
	insert(&root, 10);
	insert(&root, 13);
	insert(&root, 18);
	insert(&root, 23);
	insert(&root, 6);
	insert(&root, 7);

	delete(&root, search(root, 15));
	inorder_tree(root);
	delete(&root, search(root, 5));
	inorder_tree(root);
	delete(&root, search(root, 16));
	inorder_tree(root);
	delete(&root, search(root, 3));
	inorder_tree(root);
	delete(&root, search(root, 12));
	inorder_tree(root);
	delete(&root, search(root, 20));
	inorder_tree(root);
	delete(&root, search(root, 10));
	inorder_tree(root);
	delete(&root, search(root, 13));
	inorder_tree(root);
	delete(&root, search(root, 18));
	inorder_tree(root);
	delete(&root, search(root, 23));
	inorder_tree(root);
	delete(&root, search(root, 6));
	inorder_tree(root);
	delete(&root, search(root, 7));
	inorder_tree(root);

	inorder_tree(root);

	return 0;
}
